package oj_leetcode;

public class MedianOfTwoSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double res;
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0) {
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) * 1.0 / 2;
            } else {
                return nums2[(n - 1) / 2];
            }
        } else if (n == 0) {
            if (m % 2 == 0) {
                return (nums1[m / 2 - 1] + nums1[m / 2]) * 1.0 / 2;
            } else {
                return nums1[(m - 1) / 2];
            }
        }
        int gap = (m + n - 1) / 2;
        // (k+1) + (j+1) = gap
        int k; // list1的开始位置
        int j;// list2的开始位置
        if (m > n) {
            k = Math.min(m, gap) - 1 - 1; // list1的开始位置
            j = gap - k - 1 - 1; // list2的开始位置
        } else {
            j = Math.min(n, gap) - 1 - 1; // list1的开始位置
            k = gap - j - 1 - 1; // list2的开始位置
        }
        int lb1 = -2;
        int rb1 = m;
        int lb2 = -2;
        int rb2 = n;

        if (gap == 0) {
            k = -1;
            j = -1;
        } else if (gap == 1) {
            if (nums1[0] > nums2[0]) {
                k = -1;
                j = 0;
            } else {
                k = 0;
                j = -1;
            }
        }

        while (j >= 0 && k >= 0) {
            int range;
            if (nums1[k] > nums2[j]) {
                // 确定是否需要移动
                // 确定移动多少，取小的range的1/2
                // k准备往左移动，j准备往右移动，
                // 移动完成重新规定k的右边界和j的左边界
                if (nums2[j + 1] > nums1[k]) {

                }
                if (k - lb1 > rb2 - j) {
                    range = (rb2 - j) / 2;
                } else {
                    range = (k - lb1) / 2;
                }
                // 移动
                rb1 = k;
                k = k - range;
                lb2 = j;
                j = j + range;
            } else if (nums1[k] < nums2[j]) {
                // 确定移动多少，取小的range的1/2
                // k准备往左移动，j准备往右移动，
                // 移动完成重新规定k的右边界和j的左边界
                if (rb1 - k > j - lb2) {
                    range = (j - lb2) / 2;
                } else {
                    range = (rb1 - k) / 2;
                }
                // 移动
                lb1 = k;
                k = k + range;
                rb2 = j;
                j = j - range;
            } else {
                // 相等时，移动无意义，已经是目标解了
                break;
            }
            // 结束条件检查
            if (range == 0) {
                break;
            }
        }
        // 根据k和j，得到中位数
        if ((m + n) % 2 == 1) {
            if (k == m - 1) {
                res = nums2[j + 1];
            } else if (j == n - 1) {
                res = nums1[k + 1];
            } else {
                res = Math.min(nums1[k + 1], nums2[j + 1]);
            }
        } else {
            if (k == m - 1) {
                res = nums2[j + 2] + nums2[j + 1];
            } else if (j == n - 1) {
                res = nums1[k + 2] + nums1[k + 1];
            } else {
                if (nums1[k + 1] >= nums2[j + 1]) {
                    res = nums2[j + 1];
                    j++;
                } else {
                    res = nums1[k + 1];
                    k++;
                }
                // 加第二个
                if (k == m - 1) {
                    res += nums2[j + 1];
                } else if (j == n - 1) {
                    res += nums1[k + 1];
                } else {
                    if (nums1[k + 1] >= nums2[j + 1]) {
                        res += nums2[j + 1];
                    } else {
                        res += nums1[k + 1];
                    }
                }
            }
            res = res * 1.0 / 2;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(MedianOfTwoSortedArrays.findMedianSortedArrays(new int[]{2}, new int[]{1, 3, 4, 5}));
    }


}
